The present invention relates to a traffic shaper apparatus for reducing cell variations by stabilizing the transmission timing of a cell as a unit of transmission in communication based on an asynchronous transfer mode and, more particularly, to a traffic shaper apparatus for reducing cell variations by obtaining the optimal transmission time of each cell, searching an output buffer, from which cells are cyclically read out at a predetermined rate, for an available area from which a cell is read out at the time nearest the optimal transmission time, and storing a cell in the available area.
In the asynchronous transfer mode, information is transmitted in units of relatively small packets, each consisting of fixed-length data called a cell. In performing communication based on the asynchronous transfer mode, the band can be freely changed even during communication by changing the number of cells transmitted per unit time. Each cell is switched by a node in a network to be transmitted to a target terminal. Since the transmission rate of cells varies depending on the amount of information, each node includes a buffer memory for temporarily storing cells. Incoming cells are temporarily stored in this buffer memory. Thereafter, the cells are transmitted in the order of arrival.
If the number of incoming cells momentarily increases, and the buffer memory of the node overflows, the cells are discarded in the order of increasing priority. In order to reduce the number of cells discarded, an apparatus on the transmission side, which transmits cells to a node is required to control the number of cells transmitted to a predetermined rate in a predetermined band within which no overflow occurs on the reception side. Processing of controlling the transmission rate of cells to a predetermined rate is called shaping. An apparatus for performing shaping is called a traffic shaper.
Shaping of cells must be performed in units of virtual paths which are indicated by pieces of information attached to the header portions of cells. In addition, since different bands are set for different virtual paths, the ideal cell transmission cycles vary from virtual path to virtual path. For example, a given virtual path is required to perform transmission of three cells at a time, whereas another virtual path is required to perform transmission of two cells at a time. For this reason, these virtual paths may contend with each other in terms of the ideal cell transmission time. The traffic shaper apparatus therefore has a function of arbitrating between virtual paths when their ideal transmission times overlap. A traffic shaper apparatus having such an arbitration function is disclosed in "Development of UPC and Shaping LSI for ATM network", PROCEEDINGS OF THE 1995 COMMUNICATIONS SOCIETY CONFERENCE OF THE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS, COMMUNICATION TECHNICAL REPORT, B-560, p. 227, September, 1995.
FIG. 6 shows an outline of the arrangement of a conventional traffic shaper apparatus. A traffic shaper apparatus 101 includes a ring memory 102 for temporarily buffering cells to be transmitted, and a schedule section 103 for obtaining the ideal transmission time of each cell. The ring memory 102 includes a predetermined number of storage areas for storing cells. An identification number is assigned to each storage area.
A counter 104 sequentially and repeatedly counts identification numbers up to the total number of storage areas in the ring memory 102. The count value of the counter 104 indicates a value corresponding to the read pointer of the ring memory 102. Cells are cyclically read out from the ring memory 102 at a predetermined rate in accordance with the counting of the counter 104. The cells read out from the ring memory 102 are sequentially output to a transmission path.
A contention control circuit 105 includes register circuits 111 equal in number to the storage areas in the ring memory 102. Each register circuit 111 stores 1-bit flag information indicating whether a corresponding storage area of the ring memory 102 is available or not. A decoder 106 receives information about the ideal transmission time from the schedule section 103, and obtains an identification number corresponding to the area, in the ring memory 102, from which a cell is read out at the time. The decoder 106 also decodes the obtained identification number, and outputs a start position signal indicating the search start position to the corresponding register circuit 111 of the contention control circuit 105. Upon reception of the start position signal from the decoder 106, the contention control circuit 105 checks the flag information in the corresponding register circuit 111 to determine whether the corresponding area is available or not.
If the area is available, the contention control circuit 105 changes the flag information in the corresponding register circuit 111 into information indicating that the area is not available. At the same time, the contention control circuit 105 stores the cell in the corresponding storage area in the ring memory 102. If the ideal storage area is not available, the contention control circuit 105 sequentially searches the register circuits 111 for an available area in the direction in which the transmission time becomes later, and stores the cell in the corresponding area in the ring memory 102.
FIG. 7 shows an example of a search procedure by which the contention control circuit in FIG. 6 searches for an available area. The contention control circuit includes register circuits 111.sub.21 to 111.sub.32 equal in number to the storage areas in the ring memory 102. Each register circuit stores flag information indicating whether a corresponding area in the ring memory 102 is available or not. FIG. 7 shows some of the N register circuits. Identification numbers "adr. 21" to "adr. 32" are respectively assigned to the register circuits 111.sub.21 to 111.sub.32.
The flag information held in each register circuit is notified to the register circuit on the subsequent state in the direction in which cells are read out from the ring memory 102. Referring to FIG. 7, each register circuit in which "1" is written indicates that a corresponding area is not available, and each register circuit in which "0" is written indicates that a corresponding area is available.
Assume that the identification number of the area corresponding to the ideal transmission time of the current cell is "adr. 24". In this case, a search is started from the register circuit 111.sub.24 corresponding to this identification number. Referring to FIG. 7, a search route is indicated by a dotted line 112. In this case, since the register circuit 111.sub.24 as the search start point is not available, the search proceeds in the direction in which the identification number increases (the readout time order). The register circuits up to the register circuit 111.sub.28 with "adr. 28" are not available, and the register circuit 111.sub.29 with "adr. 29" is the first available register circuit after the search is started. The area indicated by the identification number "adr. 29" is therefore determined as the current cell storage area.
Subsequently, the contention control circuit 105 changes the flag information in the register circuit 111.sub.29 into "1" indicating that the corresponding area is not available, and passes the identification number "adr. 29" as write address information to the ring memory 102. As described above, if the area corresponding to the ideal transmission time has already been used by a cell on another virtual path, a sequential search is performed toward the future to find an available storage area from which a cell is read out at the time nearest the ideal transmission time.
A series of operations of obtaining an ideal transmission time, searching out an available area closest to the ideal transmission time, and storing a cell in the area must be completed within a time interval in which each cell arrives. However, in a conventional traffic shaper apparatus, since a sequential search is started from the position (area) corresponding to the ideal transmission time to find an available area, if unavailable areas continue, it takes time to fine an available area. For this reason, the ring memory 102 having a relatively small storage capacity must be used to complete a search within a one-cell time. Therefore, cell delay variation (CDV) cannot be sufficiently reduced.